class Solution {
public:
    int ret = 0;
    int dx[4] = { 0, 0, -1, 1 };
    int dy[4] = { -1, 1, 0, 0 };
    void dfs(vector<vector<int>>& grid, int i, int j, int step, int end)
    {
        if(grid[i][j] == 2)
        {
            if(step == end) ret++;
            return;
        }
        grid[i][j] = -1;

        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() && grid[x][y] != -1)
                dfs(grid, x, y, step + 1, end);
        }

        grid[i][j] = 0;
    }
    int uniquePathsIII(vector<vector<int>>& grid) {
        int x = 0, y = 0, cnt = 0;
        for(int i = 0; i < grid.size(); i++)
        {
            for(int j = 0; j < grid[0].size(); j++)
            {
                if(grid[i][j] == 1) 
                    x = i, y = j;
                else if(grid[i][j] == -1)
                    cnt++;
            }
        }
        dfs(grid, x, y, 1, grid.size() * grid[0].size() - cnt);
        return ret;
    }
};